﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace T9
{
    /// <summary>
    /// A class representing a predictive text engine that is based
    /// on a dictionary of valid words
    /// </summary>
    public class T9Engine
    {
        /// <summary>
        /// The relative path to the list of valid words
        /// </summary>
        private const String RELATIVE_DICTIONARY_PATH = "~/english-words.txt";

        private const char INVALID_INPUT_CHAR = '-';

        /// <summary>
        /// A map of letters to digits
        /// </summary>
        private static readonly Dictionary<char, int> LetterMap =
            new Dictionary<char, int>
        {
            {'a',2}, {'b',2}, {'c',2},
            {'d',3}, {'e',3}, {'f',3},
            {'g',4}, {'h',4}, {'i',4},
            {'j',5}, {'k',5}, {'l',5},
            {'m',6}, {'n',6}, {'o',6},
            {'p',7}, {'q',7}, {'r',7}, {'s',7},
            {'t',8}, {'u',8}, {'v',8},
            {'w',9}, {'x',9}, {'y',9}, {'z',9}
        };

        private T9Tree _WordTree = new T9Tree();

        /// <summary>
        /// A class representing a tree structure of valid
        /// words and prefixes
        /// </summary>
        private class T9Tree
        {
            private T9Tree _Parent;
            private Boolean _IsLeaf;
            private Dictionary<char, T9Tree> _Children;

            public List<string> ValidWords = new List<string>();
            public List<String> ValidPrefixes = new List<string>();

            /// <summary>
            /// A constructor which sets up the root of a T9Tree
            /// </summary>
            public T9Tree()
            {
                _Parent = null;
                _IsLeaf = true;
                _Children = new Dictionary<char, T9Tree>();
                //ValidWords.Add("");
                //ValidPrefixes.Add("");
            }//end T9Tree()

            /// <summary>
            /// A constructor which sets up a child T9Tree
            /// </summary>
            /// <param name="theParent"></param>
            public T9Tree(T9Tree theParent)
            {
                _Parent = theParent;
                _IsLeaf = true;
                _Children = new Dictionary<char, T9Tree>();
            }//end T9Tree(T9Tree)

            /// <summary>
            /// Adds a valid word to the T9Tree
            /// </summary>
            /// <param name="digitString">The digit representation of the word</param>
            /// <param name="letterString">The actual word</param>
            public void Add(string digitString, string letterString)
            {
                Add(digitString, letterString, 0);
            }//end Add(string,string)

            /// <summary>
            /// Adds a valid word to the T9Tree
            /// </summary>
            /// <param name="digitString">The digit representation of the word</param>
            /// <param name="letterString">The actual word</param>
            /// <param name="prefixLength">
            /// The number of characters already added to the tree
            /// </param>
            public void Add(string digitString, string letterString, int prefixLength = 0)
            {
                System.Diagnostics.Debug.Assert(digitString.Length == letterString.Length);
                System.Diagnostics.Debug.Assert(digitString.Length > 0);

                if (prefixLength == digitString.Length)
                {
                    ValidWords.Add(letterString);
                    return;
                }//end if
                else
                {
                    if (_IsLeaf)
                        _IsLeaf = false;
                    ValidPrefixes.Add(letterString.Substring(0, prefixLength));
                    char currentChar = digitString.ElementAt<char>(prefixLength);
                    if (_Children.ContainsKey(currentChar))
                        _Children[currentChar].Add(digitString, letterString, ++prefixLength);
                    else
                    {
                        T9Tree newChild = new T9Tree(this);
                        newChild.Add(digitString, letterString, ++prefixLength);
                        _Children.Add(currentChar, newChild);
                    }//end if else
                        
                }//end else


            }//end Add(string,string)

            /// <summary>
            /// Gets a child tree based on it's digit
            /// </summary>
            /// <param name="childToFind">The digit of the child to find</param>
            /// <returns>A T9Tree</returns>
            public T9Tree GetChild(char childToFind)
            {
                if (_Children.ContainsKey(childToFind))
                {
                    return _Children[childToFind];
                }
                else
                    return null;
            }//end T9Tree Traverse(char)

        }//end class T9Tree
        
        /// <summary>
        /// A constructor which builds a T9Tree from a list of valid words
        /// </summary>
        public T9Engine()
        {
            string fileLine = String.Empty;
            string mappedWord = String.Empty;

            var path = System.Web.Hosting.HostingEnvironment.MapPath(RELATIVE_DICTIONARY_PATH);
            using (var dictionaryFile = File.OpenText(path))
            {
                while ((fileLine = dictionaryFile.ReadLine()) != null)
                {
                    mappedWord = LettersToDigits(fileLine);
                    _WordTree.Add(mappedWord, fileLine);
                }//end while
            }//end using StreamReader
        }//end T9Engine()

        /// <summary>
        /// Find a T9Tree based on a string of digits
        /// </summary>
        /// <param name="digitPath">The string of digits</param>
        /// <param name="lastNodeFound">
        /// An output parameter representing the T9Tree child 
        /// found by traversing the string of digits
        /// </param>
        /// <returns>True if the digit path was valid, otherwise false</returns>
        private Boolean FindNode(String digitPath, out T9Tree lastNodeFound)
        {
            T9Tree currentNode = _WordTree;
            T9Tree nextNode;

            foreach (char digit in digitPath)
            {
                lastNodeFound = currentNode;
                nextNode = currentNode.GetChild(digit);
                if (nextNode == null)
                    return false;
                currentNode = nextNode;
            }//end foreach
            lastNodeFound = currentNode;
            return true;

        }//end FindNode

        /// <summary>
        /// Gets a list of valid words an valid prefixes
        /// based on an input string
        /// </summary>
        /// <param name="input">The input string to find in the tree</param>
        /// <param name="wordList">Output list of valid words</param>
        /// <param name="prefixList">Output list of valid prefixes</param>
        /// <returns>
        /// True if the input string was found in the tree, otherwise false
        /// </returns>
        public Boolean GetWordsAndPrefixes(String input, out List<String> wordList, out List<String> prefixList)
        {
            T9Tree node;
            if (FindNode(input, out node))
            {
                wordList = node.ValidWords;
                prefixList = node.ValidPrefixes;
                return true;
            }
            else
            {
                String temp = String.Empty;
                foreach (var ch in input)
                    temp += INVALID_INPUT_CHAR.ToString();
                wordList = new List<String> { temp };
                prefixList = new List<String> { temp };
                return false;
            }//end if else

        }//end Boolean GetWordsAndPrefixes(String, out List<String>, out List<String>)

        /// <summary>
        /// maps a word to a string of digits
        /// </summary>
        /// <param name="word">The word to map</param>
        /// <returns>The string of digits</returns>
        public static String LettersToDigits(string word)
        {
            word = word.ToLower();
            string mappedWord = String.Empty;
            foreach (char letter in word)
            {
                System.Diagnostics.Debug.Assert('a' <= letter && letter <= 'z');
                mappedWord += LetterMap[letter].ToString();
            }//end foreach letter
            return mappedWord;
        }//end LettersToDigits
    }

}//end namespace T9
